Міністерство освіти і науки, молоді і спорту України Національний технічний університет України «Київский політехнічний інститут» Навчально-науковий комплекс «Інститут прикладного системного аналізу» Кафедра Системного Проектування Курсова робота З дисципліни «Програмування і алгоритмічні мови» «Обхід дерев» Зміст Вступ 2 Теоретична частина 4 Обробка даних у вершинах дерева 5  Лівий спадний обхід 6  Лівий висхідний обхід 6  Лівий змішаний обхід 7 Приклад лівого спадного обходу LPreorder 10 Перелік використаної літератури 11 Код програми реалізації обходу дерев мовою С. 12 Вступ Ця робота присвячена дослідженню засобів обходу дерев. На сьогоднішній день дерева є найбільш поширеною структурою. Вони використовуються майже в кожній галузі, що стосується програмування, моделювання інформаційних процесів, комунікаційних систем, системного аналізу і систематизації взагалі. Вони популярні серед людей з технічним напрямком занять, і не дарма: дерева забезпечують найшвидші і найоптимальніші умови для знаходження елемента серед інших в певній структурі. Звичайно, існують багато типів дерев, в залежності від мети їх створення, і багато операцій над деревами: створення дерева, включення елемента в дерево, обробка даних у вершинах дерев, видалення елемента з дерева, збереження і відновлення бінарного дерева, знищення бінарного дерева. Але в будь-якому дереві найважливішою операцією все одно залишатиметься пошук (локалізація) елемента в дереві, бо на ній побудовані ледь не всі інші операції. Наприклад, включення елемента в дерево складається з трьох дій: пошуку місця включення, виділення динамічної пам’яті і безпосереднього занесення даних. При чому при пошуку місця для елемента ми повинні впевнитись у тому, що такого елемента ще не існує в цьому дереві. А це означає ще одну операцію обходу. Взагалі, дерева – це така структура, що забезпечує найоптимальніші умови зберігання даних і також найменший час їх пошуку, а в збалансованих деревах взагалі можна знайти елемент зробивши лише один крок. Недарма розв’язанням проблем, пов’язаних з деревами, займаються не тільки національні і державні університети та дослідницькі інститути, а ще й великі комерційні підприємства та фірми. У дерева пошуку, дерева сортування й у взагалі таку область дискретної математики, як дерева вкладено величезну купу грошей, нескінченні роки розумової праці найяскравіших інтелектуалів планети. Проте щоб збалансовані дерева залишалися такими при тому, що в них зберігатимуться величезні об’єми даних, треба винайти ще більш ефективні методи обходу дерев, що займають менше часу і, крім того, ще б по ходу дєла сортували данні у відповідності з принципами, що я наводжу у теоретичній частині. Саме такі задачі поставлені перед нашою сьогоднішньою технічною елітою, і перед нами в тому ж числі. Теоретична частина Обхід дерев найчастіше проходить задля пошуку елемента. А пошук елемента має на меті різні завдання. По-перше, визначити, чи належить шуканий елемент дереву, чи ні. В цьому випадку результатом буде повернення ознаки про наявність елемента чи його відсутність( true or false, 1 чи 0 відповідно). По-друге, пошук з метою вибірки й опрацювання даних елементу, тоді результат пошуку повертається у вигляді адреси вершини. По-третє, пошук з метою видалення елементу, такий пошук часто є лиш частиною повної операції видалення, а не самостійною операцією. Сам алгоритм пошуку залежить від виду дерева. В ідеально збалансованому дереві пошук доводиться проводити обходом вершин в деякій послідовності. Мінімальна довжина пошуку тоді дорівнює 1, максимальна ж – n, ну а середня тоді – n/2. Алгоритм пошуку в бінарному дереві пошуку, як в простому, так і в збалансованому, достатньо простий. Пошук проходить цілеспрямованим рухом вздовж ребер дерева. Якщо ключ пошуку дорівнює ключу у вершині, тоді ключ вважається знайденим і його адреса повертається через параметр-вказівник. Якщо ж ключ пошуку менший від ключа у вершині, тоді ми рухаємося по лівому піддереву, якщо ж навпаки, то ...